<head>
    <meta charset="UTF-8">
<title>算法训练 Don't fear, DravDe is kind</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <!--[if gte mso 9]><xml>
<w:WordDocument>
<w:View>Normal</w:View>
<w:Zoom>0</w:Zoom>
<w:TrackMoves />
<w:TrackFormatting />
<w:PunctuationKerning />
<w:DrawingGridVerticalSpacing>7.8 磅</w:DrawingGridVerticalSpacing>
<w:DisplayHorizontalDrawingGridEvery>0</w:DisplayHorizontalDrawingGridEvery>
<w:DisplayVerticalDrawingGridEvery>2</w:DisplayVerticalDrawingGridEvery>
<w:ValidateAgainstSchemas />
<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
<w:IgnoreMixedContent>false</w:IgnoreMixedContent>
<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
<w:DoNotPromoteQF />
<w:LidThemeOther>EN-US</w:LidThemeOther>
<w:LidThemeAsian>ZH-CN</w:LidThemeAsian>
<w:LidThemeComplexScript>X-NONE</w:LidThemeComplexScript>
<w:Compatibility>
<w:SpaceForUL />
<w:BalanceSingleByteDoubleByteWidth />
<w:DoNotLeaveBackslashAlone />
<w:ULTrailSpace />
<w:DoNotExpandShiftReturn />
<w:AdjustLineHeightInTable />
<w:BreakWrappedTables />
<w:SnapToGridInCell />
<w:WrapTextWithPunct />
<w:UseAsianBreakRules />
<w:DontGrowAutofit />
<w:SplitPgBreakAndParaMark />
<w:DontVertAlignCellWithSp />
<w:DontBreakConstrainedForcedTables />
<w:DontVertAlignInTxbx />
<w:Word11KerningPairs />
<w:CachedColBalance />
<w:UseFELayout />
</w:Compatibility>
<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
<m:mathPr>
<m:mathFont m:val="Cambria Math" />
<m:brkBin m:val="before" />
<m:brkBinSub m:val="--" />
<m:smallFrac m:val="off" />
<m:dispDef />
<m:lMargin m:val="0" />
<m:rMargin m:val="0" />
<m:defJc m:val="centerGroup" />
<m:wrapIndent m:val="1440" />
<m:intLim m:val="subSup" />
<m:naryLim m:val="undOvr" />
</m:mathPr></w:WordDocument>
</xml><![endif]-->
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:10.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;color:black;
mso-themecolor:text1;mso-font-kerning:0pt">【问题描述】</span><span style="font-size:
12.0pt;font-family:宋体;mso-bidi-font-family:宋体;color:black;mso-themecolor:text1;
mso-font-kerning:0pt"> </span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:10.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;color:black;
mso-themecolor:text1;mso-font-kerning:0pt">这一天，有一列车子排起了一排长队，必经之路是一个被魔王</span><span style="font-size:10.0pt;font-family:宋体;mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;mso-fareast-font-family:宋体;mso-fareast-theme-font:
minor-fareast;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;color:black;mso-themecolor:text1;mso-font-kerning:0pt">笼罩的山洞。每辆车的司机害怕魔王程度不同，所以每个司机有一些要求。</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:10.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;color:black;
mso-themecolor:text1;mso-font-kerning:0pt">车子有</span><span lang="EN-US" style="font-size:10.0pt;mso-ascii-font-family:Calibri;mso-fareast-font-family:
宋体;mso-hansi-font-family:Calibri;mso-bidi-font-family:宋体;color:black;
mso-themecolor:text1;mso-font-kerning:0pt">n</span><span style="font-size:10.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;color:black;
mso-themecolor:text1;mso-font-kerning:0pt">台，排成一条长队，每辆车有</span><span lang="EN-US" style="font-size:10.0pt;mso-ascii-font-family:Calibri;mso-fareast-font-family:
宋体;mso-hansi-font-family:Calibri;mso-bidi-font-family:宋体;color:black;
mso-themecolor:text1;mso-font-kerning:0pt">4</span><span style="font-size:10.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;color:black;
mso-themecolor:text1;mso-font-kerning:0pt">个属性</span><span lang="EN-US" style="font-size:10.0pt;mso-ascii-font-family:Calibri;mso-fareast-font-family:
宋体;mso-hansi-font-family:Calibri;mso-bidi-font-family:宋体;color:black;
mso-themecolor:text1;mso-font-kerning:0pt">:</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span lang="EN-US" style="font-size:10.0pt;mso-ascii-font-family:Calibri;mso-fareast-font-family:
宋体;mso-hansi-font-family:Calibri;mso-bidi-font-family:宋体;color:black;
mso-themecolor:text1;mso-font-kerning:0pt">V<span style="mso-spacerun:yes">&nbsp; </span></span><span style="font-size:10.0pt;font-family:宋体;mso-ascii-font-family:
Calibri;mso-ascii-theme-font:minor-latin;mso-fareast-font-family:宋体;mso-fareast-theme-font:
minor-fareast;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;color:black;mso-themecolor:text1;mso-font-kerning:0pt">&mdash;&mdash;这辆车的总价值，价值就是比如它其中的乘客和货物的价值</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span lang="EN-US" style="font-size:10.0pt;mso-ascii-font-family:Calibri;mso-fareast-font-family:
宋体;mso-hansi-font-family:Calibri;mso-bidi-font-family:宋体;color:black;
mso-themecolor:text1;mso-font-kerning:0pt">c<span style="mso-spacerun:yes">&nbsp; </span></span><span style="font-size:10.0pt;font-family:宋体;mso-ascii-font-family:
Calibri;mso-ascii-theme-font:minor-latin;mso-fareast-font-family:宋体;mso-fareast-theme-font:
minor-fareast;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;color:black;mso-themecolor:text1;mso-font-kerning:0pt">&mdash;&mdash;这辆车里面的人数量（司机表示自己也算一个乘客，司机和乘客不用区分开来）</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span lang="EN-US" style="font-size:10.0pt;mso-ascii-font-family:Calibri;mso-fareast-font-family:
宋体;mso-hansi-font-family:Calibri;mso-bidi-font-family:宋体;color:black;
mso-themecolor:text1;mso-font-kerning:0pt">l<span style="mso-spacerun:yes">&nbsp; </span></span><span style="font-size:10.0pt;font-family:宋体;mso-ascii-font-family:
Calibri;mso-ascii-theme-font:minor-latin;mso-fareast-font-family:宋体;mso-fareast-theme-font:
minor-fareast;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;color:black;mso-themecolor:text1;mso-font-kerning:0pt">&mdash;&mdash;在这辆车的前面需要总量正好为多少乘客的车（不多也不少），这车才敢开</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span lang="EN-US" style="font-size:10.0pt;mso-ascii-font-family:Calibri;mso-fareast-font-family:
宋体;mso-hansi-font-family:Calibri;mso-bidi-font-family:宋体;color:black;
mso-themecolor:text1;mso-font-kerning:0pt">r<span style="mso-spacerun:yes">&nbsp; </span></span><span style="font-size:10.0pt;font-family:宋体;mso-ascii-font-family:
Calibri;mso-ascii-theme-font:minor-latin;mso-fareast-font-family:宋体;mso-fareast-theme-font:
minor-fareast;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;color:black;mso-themecolor:text1;mso-font-kerning:0pt">&mdash;&mdash;在这辆车的后面需要总量正好为多少乘客的车（不多也不少），这车才敢开</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span lang="EN-US" style="font-size:10.0pt;mso-bidi-font-family:宋体;color:black;mso-themecolor:
text1;mso-font-kerning:0pt"><span style="mso-spacerun:yes">&nbsp;</span></span><span style="font-size:10.0pt;font-family:宋体;mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;mso-fareast-font-family:宋体;mso-fareast-theme-font:
minor-fareast;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;color:black;mso-themecolor:text1;mso-font-kerning:0pt">&ldquo;前面需要总量正好为多少乘客的车&rdquo;指的是驶在这辆车前面所有的车的乘客总数。</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;text-indent:5.0pt;mso-char-indent-count:.5;mso-pagination:
widow-orphan"><span style="font-size:10.0pt;font-family:宋体;mso-ascii-font-family:
Calibri;mso-ascii-theme-font:minor-latin;mso-fareast-font-family:宋体;mso-fareast-theme-font:
minor-fareast;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;color:black;mso-themecolor:text1;mso-font-kerning:0pt">&ldquo;后面需要总量正好为多少乘客的车&rdquo;指的是驶在这辆车后面所有的车的乘客总数。</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:10.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;color:black;
mso-themecolor:text1;mso-font-kerning:0pt"><span style="font-size:10.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;color:black;
mso-themecolor:text1;mso-font-kerning:0pt">你</span>不能改变每辆车在车队的相对顺序，但你可以安排某些车退出车队，保证依然在车队的每辆车都敢开了，即满足上述条件，并且剩下车的</span><span lang="EN-US" style="font-size:10.0pt;mso-ascii-font-family:Calibri;mso-fareast-font-family:
宋体;mso-hansi-font-family:Calibri;mso-bidi-font-family:宋体;color:black;
mso-themecolor:text1;mso-font-kerning:0pt">v</span><span style="font-size:10.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;color:black;
mso-themecolor:text1;mso-font-kerning:0pt">的总量最大。</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span lang="EN-US" style="font-size:10.0pt;font-family:宋体;mso-bidi-font-family:宋体;color:black;
mso-themecolor:text1;mso-font-kerning:0pt">-----------------------------<br />
</span><span style="font-size:12.0pt;font-family:宋体;mso-bidi-font-family:宋体;
mso-font-kerning:0pt">简单来说，给您按输入顺序排列的<span lang="EN-US">n</span>辆车，您需要删去里面的一些车（剩下的车仍然按原相对顺序排列）。</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:12.0pt;
font-family:宋体;mso-bidi-font-family:宋体;mso-font-kerning:0pt">使得对于每辆车，若它没被删去，设其为输入的第<span lang="EN-US">i</span>辆车，</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:12.0pt;
font-family:宋体;mso-bidi-font-family:宋体;mso-font-kerning:0pt">要满足</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span lang="EN-US" style="font-size:12.0pt;font-family:宋体;mso-bidi-font-family:宋体;mso-font-kerning:
0pt">l[i]= sigma{c[j] | j&lt;i </span><span style="font-size:12.0pt;font-family:
宋体;mso-bidi-font-family:宋体;mso-font-kerning:0pt">且第<span lang="EN-US">j</span>辆车没被删去<span lang="EN-US">}</span></span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span lang="EN-US" style="font-size:12.0pt;font-family:宋体;mso-bidi-font-family:宋体;mso-font-kerning:
0pt">r[i]= sigma{c[j] | j&gt;i </span><span style="font-size:12.0pt;font-family:
宋体;mso-bidi-font-family:宋体;mso-font-kerning:0pt">且第<span lang="EN-US">j</span>辆车没被删去<span lang="EN-US">}</span></span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:12.0pt;
font-family:宋体;mso-bidi-font-family:宋体;mso-font-kerning:0pt">在满足这些条件前提下，要求<span lang="EN-US">sigma{V[i] | i</span>没被删去<span lang="EN-US">} </span>最大，</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:12.0pt;
font-family:宋体;mso-bidi-font-family:宋体;mso-font-kerning:0pt">请输出这个最大值，并且递增输出没有被删去的车的标号。</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span lang="EN-US" style="font-size:12.0pt;font-family:宋体;mso-bidi-font-family:宋体;mso-font-kerning:
0pt">&nbsp;</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:10.0pt;
font-family:宋体;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;mso-font-kerning:0pt">【输入格式】</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:12.0pt;
font-family:宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:
0pt">输入的第一行为一个正整数</span><span lang="EN-US" style="font-size:12.0pt;mso-ascii-font-family:
Calibri;mso-fareast-font-family:宋体;mso-hansi-font-family:Calibri;mso-bidi-font-family:
宋体;mso-font-kerning:0pt">n</span><span style="font-size:12.0pt;font-family:
宋体;mso-ascii-font-family:Calibri;mso-ascii-theme-font:minor-latin;mso-fareast-font-family:
宋体;mso-fareast-theme-font:minor-fareast;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt">（</span><span lang="EN-US" style="font-size:12.0pt;mso-ascii-font-family:Calibri;mso-fareast-font-family:
宋体;mso-hansi-font-family:Calibri;mso-bidi-font-family:宋体;mso-font-kerning:0pt">1&lt;=n&lt;=10^5</span><span style="font-size:12.0pt;font-family:宋体;mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;mso-fareast-font-family:宋体;mso-fareast-theme-font:
minor-fareast;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;mso-font-kerning:0pt">）&mdash;&mdash;车的个数。</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:10.0pt;
font-family:宋体;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;mso-font-kerning:0pt">接下来<span lang="EN-US">n</span>行，每行四个整数，第<span lang="EN-US">i</span>行的数字<span lang="EN-US">: vi, ci,li ,</span></span><span lang="EN-US" style="font-size:14.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt">r<sub>i</sub> </span><span lang="EN-US" style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:
0pt">,</span><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:
Calibri;mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:
0pt">（<span lang="EN-US">1&lt;=vi&lt;=10^4 , 1&lt;=ci&lt;=10^5,0&lt;=li,ri&lt;=10^5</span>），车子们从<span lang="EN-US">1</span>开始编号，从车队的最前头开始算起。</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span lang="EN-US" style="font-size:10.0pt;font-family:宋体;mso-bidi-font-family:宋体;mso-font-kerning:
0pt">&nbsp;</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:10.0pt;
font-family:宋体;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;mso-font-kerning:0pt">【输出格式】</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:10.0pt;
font-family:宋体;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;mso-font-kerning:0pt">第一行输出一个数<span lang="EN-US">k</span>：会继续在这车队里的车的总数（注意我们的目标是让价值最大）。</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:10.0pt;
font-family:宋体;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;mso-font-kerning:0pt">第二行<span lang="EN-US">k</span>个数，递增输出继续在车队里的车的编号。</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:10.0pt;
font-family:宋体;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;mso-font-kerning:0pt">请留心你不允许改变车的次序。如果答案不唯一，输出任意一个。</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan">&nbsp;</p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">【样例输入】</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-bidi-font-family:宋体;mso-font-kerning:
0pt;mso-ansi-language:ZH-CN">&nbsp;</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">5</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">1 1 0 3</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">1 1 1 2</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">1 1 2 1</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">1 1 3 0</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">2 1 3 0</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-bidi-font-family:宋体;mso-font-kerning:
0pt;mso-ansi-language:ZH-CN">&nbsp;</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">【样例输出】</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-bidi-font-family:宋体;mso-font-kerning:
0pt;mso-ansi-language:ZH-CN">&nbsp;</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">4</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">1 2 3 5 </span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-bidi-font-family:宋体;mso-font-kerning:
0pt;mso-ansi-language:ZH-CN">&nbsp;</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">【样例输入】</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-bidi-font-family:宋体;mso-font-kerning:
0pt;mso-ansi-language:ZH-CN">&nbsp;</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">5</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">1 1 0 3</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">10 1 2 1</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">2 2 1 1</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">10 1 1 2</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">3 1 3 0</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-bidi-font-family:宋体;mso-font-kerning:
0pt;mso-ansi-language:ZH-CN">&nbsp;</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">【样例输出】</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-bidi-font-family:宋体;mso-font-kerning:
0pt;mso-ansi-language:ZH-CN">&nbsp;</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">3</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan;mso-layout-grid-align:none"><span style="font-size:10.0pt;font-family:宋体;mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;mso-bidi-font-family:宋体;mso-font-kerning:0pt;
mso-ansi-language:ZH-CN">1 3 5 </span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span lang="EN-US" style="font-size:10.0pt;font-family:宋体;mso-bidi-font-family:宋体;mso-font-kerning:
0pt">&nbsp;</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:10.0pt;
font-family:宋体;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;mso-font-kerning:0pt">【数据规模与约定】</span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:10.0pt;
font-family:宋体;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;mso-font-kerning:0pt">对于<span lang="EN-US">20%</span>的数据，<span lang="EN-US">n&lt;=100</span></span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:10.0pt;
font-family:宋体;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;mso-font-kerning:0pt">对于<span lang="EN-US">50%</span>的数据，<span lang="EN-US">n&lt;=1000</span></span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:10.0pt;
font-family:宋体;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;mso-font-kerning:0pt">对于<span lang="EN-US">100%</span>的数据，<span lang="EN-US">n&lt;=100000</span></span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span style="font-size:10.0pt;
font-family:宋体;mso-hansi-font-family:Calibri;mso-hansi-theme-font:minor-latin;
mso-bidi-font-family:宋体;mso-font-kerning:0pt">对于<span lang="EN-US">100%</span>的数据，<span lang="EN-US">1&lt;=vi&lt;=10^4 , 1&lt;=ci&lt;=10^5,0&lt;=li,ri&lt;=10^5</span></span></p>
<p align="left" class="MsoNormal" style="mso-margin-top-alt:auto;mso-margin-bottom-alt:
auto;text-align:left;mso-pagination:widow-orphan"><span lang="EN-US"> </span></p>